"""
https://leetcode.cn/problems/balanced-binary-tree/description/

110. 平衡二叉树
简单
相关标签
premium lock icon
相关企业
给定一个二叉树，判断它是否是 平衡二叉树  

 

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：


输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：

输入：root = []
输出：true
 

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    平衡二叉树：
    原始定义：该树的所有节点的左右子树高度相差不超过1

    即所有虚拟空根节点的level相差值不超过1（错误的，可能出现左子树的子树，比右子树的子树level大2，但仍符合平衡二叉树条件）
    适合使用广度优先遍历

    从数学上讲，最保底的方法，是求得每个子树的高度，并对比之

    """

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        temp=[root]
        level=0
        min_level=0
        while temp:
            level+=1
            new_temp=[]
            for node in temp:
                if node:
                    new_temp.append(node.left)
                    new_temp.append(node.right)
                else:
                    if min_level==0:
                        min_level=level
                    elif level-min_level>1:
                        return False
            temp=new_temp
        
        return True
    
if __name__=='__main__':
    """
    1
    2       3
    4   5   6   None
    8
    """
    arr=[1,2,3,4,5,6,None,8]
    root=build_tree_node(arr)

    s=Solution()
    res=s.isBalanced(root)
    print(res)